package summary;

import java.util.*;

/**
 * @Author: 海琳琦
 * @Date: 2022/4/19 19:50
 */
public class Title797 {

    public static List<List<Integer>> allPathsSourceTarget(int[][] graph) {
        List<List<Integer>> result = new ArrayList<>();
        LinkedList<Integer> path = new LinkedList<>();
        path.offer(0);
        int end = graph.length;
        dfs(graph, result, 0, end, path);
        return result;
    }

    private static void dfs(int[][] graph, List<List<Integer>> result, int cur, int end, LinkedList<Integer> path) {
        if (cur == end) {
            result.add(new ArrayList<>(path));
            return;
        }
        for (int i = 0; i < graph[cur].length; i++) {
            path.offer(graph[cur][i]);
            dfs(graph, result, graph[cur][i], end, path);
            path.removeLast();
        }
    }

    public static void main(String[] args) {
        int[][] graph = {{1, 2}, {3}, {3}, {}};
        allPathsSourceTarget(graph);
    }
}
